package com.zq.solution.string;

import java.util.Stack;

/**
 * @ClassName BackspaceCompare
 * @Description 比较含退格的字符串
 * 给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
 * 注意：如果对空文本输入退格字符，文本继续为空。
 * 示例 1：
 *  输入：S = "ab#c", T = "ad#c"
 *  输出：true
 *  解释：S 和 T 都会变成 “ac”。
 * @Author ZQ
 * @Date 2020/10/19 21:46
 * @Version 1.0
 */
public class BackspaceCompare {
    public static boolean backspaceCompare(String S, String T) {
        return replaceChar1(S).equals(replaceChar1(T));
    }

    public static String replaceChar(String str){//递归实现
        if (str.contains("#")){
            int index = str.indexOf('#');
            String s = "";
            if (index == 0){
                s = str.substring(1,str.length());
            }else {
                s = str.substring(0,index - 1) + str.substring(index + 1,str.length()) ;
            }
            str = replaceChar(s);
        }
        return str;
    }
    public static String replaceChar1(String str){//使用栈实现
        Stack<Character> stack = new Stack<>();
        for (Character c : str.toCharArray()){
            if (c.equals('#')){
                if (stack.size() != 0)  stack.pop();
            }else {
                stack.push(c);
            }
        }
        return stack.toString();
    }


    public static void main(String[] args) {
        String S = "a#c", T = "b";
        System.out.println(backspaceCompare(S,T));
    }
}
